1848D - Vika and Bonuses - CodeForces Solution

#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops",                  \
                         "omit-frame-pointer", "inline")
#pragma GCC target(                                                            \
        "sse,sse2,sse3,ssse3,sse4,sse4.1,sse4.2,popcnt,abm,mmx,avx,avx2,fma,tune=native")
#pragma GCC option("arch=native", "no-zero-upper") // Enable AVX

/// UH Top
#include <bits/stdc++.h>
#define db(x)   cerr << #x << ':' << (x) << '\n';
#define all(v)  (v).begin(), (v).end()
#define allr(v) (v).rbegin(), (v).rend()
// #define int ll
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
// typedef __int128_t int128;
typedef pair<ll, ll> pii;
typedef pair<ld, ll> pdi;
typedef pair<ld, ld> pdd;
typedef pair<ld, pdd> pdp;
typedef pair<string, ll> psi;
typedef pair<ll, string> pls;
typedef pair<string, string> pss;
typedef pair<ll, pii> pip;
typedef pair<pii, pii> ppp;
typedef complex<ld> point;
typedef vector<point> polygon;
typedef vector<ll> vi;
typedef pair<point, int> ppi;
#define prec(n)                                                                \
	cout.precision(n);                                                         \
	cout << fixed
const ll mod = (1e9 + 7);
const ld eps = (1e-9);
const ll oo = (ll)(1e18 + 5);
#define pi   acos(-1)
#define MAXN (ll)(1e6 + 5)

int nxt[10][30];
ll add[10][30];

ll adv(ll s, int k) {
	ll base = s % 10;
	ll ans = s;
	for (int po = 0; po < 30; po++)
		if (k & (1 << po)) {
			ans += add[base][po];
			base = nxt[base][po];
		}
	return ans;
}

int32_t main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	for (int i = 0; i < 10; i++) {
		nxt[i][0] = (2 * i) % 10;
		add[i][0] = i;
	}
	for (int j = 1; j < 30; j++)
		for (int i = 0; i < 10; i++) {
			nxt[i][j] = nxt[nxt[i][j - 1]][j - 1];
			add[i][j] = add[i][j - 1] + add[nxt[i][j - 1]][j - 1];
		}

	int t;
	cin >> t;
	while (t--) {
		ll s, k;
		cin >> s >> k;
		// for(int i=0;i<100;i++)
		//     cout << adv(s, i)*(k-i) << '\n';
		ll upg = 0;
		for (int po = (1 << 29); po; po >>= 1)
			if ((upg + po) * 4 <= k &&
			    adv(s, (upg + po - 1) * 4) * (k - (upg + po - 1) * 4) <
			        adv(s, (upg + po) * 4) * (k - (upg + po) * 4))
				upg += po;
		ll ans = 0;
		// cout << upg << '\n';
		upg *= 4;
		ll last = s;
		int best = 0;
		for (int i = 0; i < 10; i++) {
			if (i <= k) {
				ans = max(ans, last * (k - i));
				last = (last + (last % 10));
			}
		}
		last = -1;
		for (int i = -100; i <= 100; i++)
			if (upg + i >= 0 && upg + i <= k) {
				ll mul;
				if (last == -1)
					mul = adv(s, upg + i);
				else
					mul = (last + (last % 10));
				last = mul;
				if (mul * (k - upg - i) > ans)
					best = upg + i;
				ans = max(ans, mul * (k - upg - i));
			}
		// cout << best << '\n';

		cout << ans << '\n';
	}

	return 0;
}